package subject_set.offer100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/10/15 11:43
 **/
public class Offer31 {
    class Solution {
        public boolean validateStackSequences(int[] pushed, int[] popped) {
            Deque<Integer> stack = new LinkedList<>();
            int j = 0;
            for(int i = 0; i < pushed.length; ++i){
                stack.push(pushed[i]);
                while(!stack.isEmpty() && stack.peek() == popped[j]) {
                    stack.pop();
                    j++;
                }
            }
            return stack.isEmpty();
        }
    }
}